using namespace std;

#include <map>
#include <vector>
#include <set>
#include <algorithm> // sort
#include <iostream>
namespace macl_map_sort
{

// map只能按照key进行排序。可以使用仿函数替换默认的less排序。
struct greater_by_key {
    bool operator() (const string& a, const string& b) const {
        if(a.length() == b.length()) 
            return a > b; // 长度相同时，正常字符串比较
        return a.length() > b.length(); // 否则，长度长的大
    }
};

// 重载<<操作符
ostream& operator << (ostream& out, const pair<const string, int>& p) {
    return out << p.second << "\n" << p.first.c_str();
}

void test_map_sort_by_key()
{
    map<string, int, greater_by_key> tickets;
    tickets.insert(make_pair("467623623728324", 0));
    tickets["467623623728323"] = 1;
    tickets["46762362372834"] = 2;
    tickets["56762362"] = 3;
    tickets.insert(make_pair("467623623728327", 4));

    cout << "the greatest one is: " << *(tickets.begin()) << endl;
}


// map在添加元素过程中动态的根据key和value进行排序
// from：[Dynamically sorting both keys and values](http://cplusplus.com/articles/oE3hAqkS/)
template <class _A, class _B, class _Compare=less<_A> >
class MMap : public set<pair<_A, _B>, _Compare>
{
public :
    MMap() {};
    ~MMap() {};
};

template< typename InPair >
struct MMapComp{
    bool operator() (InPair a , InPair b) const {
        if( a.first == b.first ) return a.second > b.second;
        else
            return a.first < b.first;
    }
};

void test_dynamically_sort_by_keys_and_value()
{
    MMap<char, int, MMapComp< pair<char, int>>> test;

    test.insert(make_pair('D',1));
    test.insert(make_pair('D',2));
    test.insert(make_pair('B',3));
    test.insert(make_pair('A',4));

    for(MMap<char,int>::iterator it = test.begin(); it != test.end(); it++)
        cout << (*it).first << "\t" << (*it).second << endl;
}


// map按照value进行排序，map元素构建完后，把map中元素转存到vector中，再排序
template <typename InPair>
struct less_by_value {
    bool operator() (const InPair& a, const InPair& b) const {
        return a.second < b.second;
    }
};

void test_map_sort_by_value()
{
    vector<int> nums {4, 1, 2, 1, 2};
    map<int, int> c;
    for(auto num : nums) c[num]++;

    vector<pair<int, int>> v(c.begin(), c.end());
    sort(v.begin(), v.end(), less_by_value<pair<int, int>>());

    for(auto item : v)
        cout << "(" << item.first << ", " << item.second << ")" << endl;
}
} // namespace macl_map_sort



#include <iostream>
namespace macl_vfunc
{
class A
{
public:
    virtual void F() { cout << 1 << endl; }
    void CallF() { F(); }
    virtual ~A() {
        CallF();
        F();
    }
};

class B : public A
{
public:
    void F() { cout << 2 << endl; }
    ~B() {}
};

class C : public B
{
public:
    void F() { cout << 3 << endl; }
    void CallF() {
        F();
        A::CallF();
    }
    ~C() { CallF(); }
};

void test_v_func() {
    A *p = new C(); 
    p->CallF(); // 3           调用 A::CallF() -V-> C::F() [输出3]
    delete p; // 3 3 1 1     析构顺序：先子类后父类，C-->B-->A
                           //  调用 C::~C() --> C::CallF() --> C::F() [输出3] --> A::CallF() -V-> C::F() [输出3]
                           //  调用 B::~B()
                           //  调用 A::~A() --> A::CallF() --> A::F() [输出1] --> A::F() [输出1]
}

} // namespace macl_vfunc


#include <queue>
#include <iostream>
namespace macl_BFS
{
// 广度优先搜索(BFS)：https://baike.baidu.com/item/%E5%AE%BD%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2/5224802?fr=aladdin&fromid=2148012&fromtitle=%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2
// 广度优先搜索在求解最短路径或者最短步数上有很多的应用。
// 应用最多的是在走迷宫上。
//
// 举例实现:
// 九度1335闯迷宫

// 在一个n*n的矩阵里走，从原点(0,0)开始走到终点(n-1,n-1)，只能上下左右4个方向走，
// 只能在给定的矩阵里走，求最短步数。
// n*n是0/1矩阵，0代表该格子没有障碍，为1表示有障碍物。

// int mazeArr[maxn][maxn]; //表示的是01矩阵
// int stepArr[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4个方向
// int visit[maxn][maxn]; //表示该点是否被访问过，防止回溯，回溯很耗时。

struct Node
{
    int x;
    int y;
    int step;
    Node(int x1, int y1, int step1) 
    : x(x1), y(y1), step(step1) {}
};

// const int maxn = 10;
// static int mazeArr[maxn][maxn] = {
//         {0, 0, 1, 0, 1, 0, 1, 0, 0, 0}, 
//         {1, 0, 0, 1, 1, 0, 1, 1, 0, 1}, 
//         {1, 0, 1, 0, 1, 0, 1, 0, 0, 1}, 
//         {1, 0, 0, 1, 0, 0, 1, 0, 1, 1}, 
//         {0, 1, 0, 0, 1, 1, 0, 1, 0, 1}, 
//         {1, 0, 1, 0, 0, 0, 1, 1, 1, 1}, 
//         {0, 1, 1, 1, 1, 0, 1, 1, 0, 1}, 
//         {1, 0, 1, 1, 1, 0, 0, 1, 0, 1}, 
//         {0, 1, 0, 1, 1, 1, 0, 0, 1, 1}, 
//         {0, 0, 1, 0, 1, 1, 0, 0, 0, 0}}; // 表示的是01矩阵


const int maxn = 5;
static int mazeArr[maxn][maxn] = {
        {0, 0, 1, 0, 1}, 
        {1, 0, 0, 1, 1}, 
        {1, 0, 1, 0, 1}, 
        {1, 0, 0, 1, 0}, 
        {0, 1, 0, 0, 0}}; // 表示的是01矩阵


// const int maxn = 3;
// static int mazeArr[maxn][maxn] = {
//         {0, 0, 1}, 
//         {1, 0, 1}, 
//         {1, 0, 0}}; // 表示的是01矩阵

static int visit[maxn][maxn] = {0}; // 表示该点是否被访问过，防止回溯，回溯很耗时。
static int stepArr[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}}; // 表示上下左右4个方向

int BFS()
{
    Node node(0, 0, 0); // 从原点(0,0)出发
    queue<Node> q;
    int n = maxn;

    // 清空队列
    while (!q.empty())
        q.pop();

    q.push(node); // 1.把根节点放到队列的末尾

    while (!q.empty())
    {
        node = q.front(); // 2.1每次从队列的头部取出一个元素
        q.pop();

        // 3.找到所要找的元素时结束程序（走到出口(n-1,n-1)，结束，返回步数）
        if (node.x == n - 1 && node.y == n - 1)
        {
            return node.step;
        }

        visit[node.x][node.y] = 1; // 标记该位置已经访问过

        // 2.2查看这个元素所有的下一级元素，把它们放到队列的末尾（每个位置的四个方法位置即下一级元素）
        for (int i = 0; i < 4; i++)
        {
            int x = node.x + stepArr[i][0];
            int y = node.y + stepArr[i][1];
            if ((x >= 0 && y >= 0) && (x < n && y < n)  // 迷宫矩阵范围内
                && visit[x][y] == 0  // 未访问
                && mazeArr[x][y] == 0) // 没有障碍
            {
                visit[x][y] = 1;
                Node next(x, y, node.step + 1); // 构造这个下一级元素放到队列末尾
                q.push(next);
            }
        }
    }

    // 4.如果遍历整个树还没有找到，结束程序
    return -1;
}

void printArr(int arr[maxn][maxn])
{
    for(int i=0; i<maxn; i++) {
        for(int j=0; j<maxn; j++) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
}

void test_BFS()
{
    printArr(mazeArr);

    int step = BFS();
    if(step == -1) {
        cout << "no path!" << endl;
        return;
    }
    cout << "the shortest step is: " << step << endl;

    printArr(visit);
}

} // namespace macl_BFS


#include <iostream>
namespace macl_cout
{
    // cout的不同进制输出
void test_cout()
{
    // [怎么用cout怎么输出带有前缀0X的数值](https://bbs.csdn.net/topics/240030733)
    // 输出指针16位地址，使用printf和cout
    void *ptr = reinterpret_cast<void *>(0x00010000);
    printf("ptr = %#p\n", ptr); // ptr = 0000000000010000
    cout << "ptr = " << std::hex << std::showbase << ptr << endl; // ptr = 0000000000010000

    int a=123, b=456, c=789;
    cout << std::dec << std::showbase << "a=" << a << ", b=" << b << ", c=" << c << endl; // a=123, b=456, c=789
    cout << std::oct << std::showbase << "a=" << a << ", b=" << b << ", c=" << c << endl; // a=0173, b=0710, c=01425
    cout << std::hex << std::showbase << "a=" << a << ", b=" << b << ", c=" << c << endl; // a=0x7b, b=0x1c8, c=0x315
}
} // namespace macl_cout


#include <string>
#include <cctype> 
// isalnum 字母数字字符。       数字、小写字母和大写字母的集合。
// isalpha 字母字符。           小写字母和大写字母的集合。
// iscntrl 控制字符。           ASCII 编码中，这些字符的八进制代码是从 000 到 037，以及 177（DEL）。
// isdigit 数字。               完整的数字集合 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }。
// isgraph 图形字符。           字母数字字符和标点符号字符的集合。
// islower 小写
// isprint 可打印字符。         字母数字字符、标点符号字符和空格字符的集合。
// ispunct 标点符号字符。       集合 { ! " # $ % & ' ( ) * + , - . / : ; < = > ? @ [ \ ] ^ _ ` { | } ~ }。
// isspace 空格字符。           制表符、换行符、垂直制表符、换页符、回车符、空格符的集合。
// isupper 大写
// isxdigit 十六进制数字。      集合 { 0 1 2 3 4 5 6 7 8 9 A B C D E F a b c d e f }。
// tolower 转小写
// toupper 转大写
// isblank 空白字符。           包括空格符和制表符。
namespace macl_cctype
{
void test_cctype()
{
    string str = "A man, a plan, a canal: Panama\n";
    cout << str.c_str() << endl;
    cout << "isalnum: "; for(auto c : str) { if(isalnum(c)) cout << c; } cout << endl;
    cout << "isalpha: "; for(auto c : str) { if(isalpha(c)) cout << c; } cout << endl;
    cout << "iscntrl: "; for(auto c : str) { if(iscntrl(c)) cout << c; } cout << endl;
    cout << "isdigit: "; for(auto c : str) { if(isdigit(c)) cout << c; } cout << endl;
    cout << "isgraph: "; for(auto c : str) { if(isgraph(c)) cout << c; } cout << endl;
    cout << "isprint: "; for(auto c : str) { if(isprint(c)) cout << c; } cout << endl;
    cout << "ispunct: "; for(auto c : str) { if(ispunct(c)) cout << c; } cout << endl;
    cout << "islower: "; for(auto c : str) { if(islower(c)) cout << c; } cout << endl;
    cout << "isupper: "; for(auto c : str) { if(isupper(c)) cout << c; } cout << endl;
}
} // namespace macl_cctype

// 汇总涵盖的字符串转换相关

// char* <--> char[]
// char* <--> std::string
// char[] <--> std::string

// char* <--> w_char*
// 

#include <iostream>
#include <string>
namespace macl_strcvt
{
void char_ptr_to_string()
{
    cout << "char_ptr_to_string()......." << endl;

    const char* cstr = "hello world, hello cpp!";
    string str(cstr); // 拷贝构造函数
    cout << str.c_str() << endl;

    string str2 = cstr; // 赋值构造函数
    cout << str2.c_str() << endl;
}

void char_array_to_string()
{
    cout << "char_array_to_string()........" << endl;

    const char cstr[256] = "hello world, hello cpp!";
    string str(cstr); // 拷贝构造
    cout << str.c_str() << endl;

    string str2 = cstr; // 赋值构造函数
    cout << str2.c_str() << endl;
}

void test_str_cvt()
{
    char_ptr_to_string();
    char_array_to_string();
   
}
} // namespace macl_strcvt




int main()
{
    // macl_map_sort::test_map_sort_by_key();
    // macl_map_sort::test_dynamically_sort_by_keys_and_value();
    // macl_map_sort::test_map_sort_by_value();

    // macl_vfunc::test_v_func();

    //macl_BFS::test_BFS();

    //macl_cout::test_cout();

    //macl_cctype::test_cctype();

    macl_strcvt::test_str_cvt();

    system("pause");
    return 0;
}